Sidus graaf

Sidus graaf on graafiteoorias graaf, milles iga kahe tipu korral leidub neid tippe ühendav ahel.

Praktilistes ülesannetes ja rakendustes käsitletakse peamiselt sidusaid graafe. Teoreetilistes ülesannetes nagu isomorfismi tuvastamisel, taastatavuse selgitamisel jne käsitletakse nii sidusaid kui ka mittesidusaid.

Väikseimat tippude arvu, mille eemaldamisel muutub graaf mittesidusaks, nimetatakse sidususarvuks k(G). Väikseimat servade arvu, mille eemaldamisel muutub graaf mittesidusaks, nimetatakse serv-sidususarvuks l(G).

Üldiselt moodustavad suurema osa graafidest sidusad graafid. Näiteks kui kolmetipuliste graafide puhul on sidusaid 50%, siis kuuetipuliste puhul on neid 71,79% ja kümnetipuliste puhul juba 97,6%. Edasiselt suureneb see veelgi ^[1].